package simple;

/**
 * 给你一个链表的头节点 head ，判断链表中是否有环。
 *
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
 * 注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。
 *
 * 如果链表中存在环，则返回 true 。 否则，返回 false 。
 *
 * 链接：https://leetcode-cn.com/problems/linked-list-cycle
 * */
public class LinkedListCycle {

    /**
     * 快慢指针法
     * 原理很简单。我们可以想象有两个正在跑步的人，一个腿长1.8m，一个腿短30公分。如果这两个人在一条直线公路上跑步，那么除了起点，他们俩再也无法碰面
     *
     * 但是如果他们在一条环形公路上跑步，腿长1.8m的人很快就能追上腿短的，也就意味着他们能再次相遇。
     * */
    public class Solution {
        public boolean hasCycle(ListNode head) {
            if(head == null){
                return false;
            }
            ListNode slow = head;
            ListNode fast = head;
            while(fast.next != null && fast.next.next != null){
                slow = slow.next;
                fast = fast.next.next;
                if(fast == slow){
                    return true;
                }
            }
            return false;
        }
    }
}
